# 搜索旋转排序数组: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
# 字节面试题，重点看下。 一遍循环写完，确实想不到。太难了


class Solution:
    def search(self, nums: list, target: int) -> int:
        """
            1. 二分查找的实现有两种方法，采用第一种：不断在循环体里面找到第一个错误的版本
            2. 抓住要点， 因为要使用二分查找法， 核心是，只有有序的区间内，才能判断出来是否有这个元素，
                这道题的关键点就变成了先判断有序区间，然后才能接着判断，元素在哪个区间，才能一步步缩小区间，然后求出结果！
            3. 观察下面步骤后其实就是一个递归的过程。 当落在有序区间了就是常规的二分查找。当落点还是无序的，那么等于又从头有序无序的判断一次， 一直缩小区间范围，对比target和 nums[mid]值
            4. 一定要注意细节！ 二分看似简单，全是细节。 错一个 =号，可能就会陷入死循环，或者程序走向错误的逻辑内！！！！ 
        """

        left, right = 0, len(nums) - 1

        # 感觉是一个递归过程
        while left <= right:
            # 1. 首先计算中间点mid   
            mid = left + (right - left) // 2    
            # 如果该点恰好等于 target，返回
            if nums[mid] == target: return mid    
            # 3. 中点必将数组分为有序和无序上来那个部分，判断哪部分有序
            if nums[left] <= nums[mid]:  # 注意这个等号不能少！ 测试用例[3, 1] 1 时。 nums[left] 和 nums[mid] 是有机会取相等的
                # 4. 前面有序，判断target在哪边
                if nums[left] <= target  and target < nums[mid]: 
                    # target在有序这边
                    right = mid - 1
                else:
                    # 在无序这边
                    left = mid + 1
            else:
                # 5. 后面有序
                if nums[mid] < target and target <= nums[right]:
                    # target在有序这边
                    left = mid + 1
                else:
                    # 在无序这边
                    right = mid - 1

        # 6. 循环计数，未找到target，那么返回 -1
        return -1


# 这是我想的，找到旋转点然后再 二分查找， 比较容易实现。
class Solution:
    def search(self, nums: list, target: int) -> int:
        """
            思路： 将数组截为两断。 旋转后的一部分一段，旋转前的一部分一段。分别再试用二分，看看能不能找到目标节点。
        """

        left, right = 0, len(nums) - 1

        # 顺序计算找出旋转点
        mid = 0
        for i in range(1, len(nums)):
            if nums[i - 1] > nums[i]:
                mid = i; break

        def binarySearch(nums, left, right, target):
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1

            return -1

        # 二分查找对应的区间： 大于最后一个元素在前面区间，小于在后面区间
        return binarySearch(nums, 0, mid - 1, target) if target > nums[-1] else binarySearch(nums, mid, len(nums) - 1, target)


nums = [3,1]
# nums = [4,5,6,7,0,1,2]

s = Solution()
rst = s.search(nums, 1)
print(rst)



